Balanced Binary Tree

Posted on |

问题描述（难度简单-110）

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

1
2
3
4
5
6
7
      1
     / \
    2   2
   / \
  3   3
 / \
4   4

Return false.

方法一：递归（Recursive）

判断平衡树是否平衡的标准：

  • 左右子树的高度差不大于1。这里的高度值得是树的最大高度。

根据标准得到一个递归公式（没有好的作图工具，直接看height函数的递归实现）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isBalanced(TreeNode root) {
       if (root == null) {
           return true;
       }
       return height(root)==-1?false:true;
   }
   public int height(TreeNode treeNode){
       if (treeNode == null) {
           return 0;
       }
       int leftHeight=height(treeNode.left);
       int rightHeight=height(treeNode.right);
       if(leftHeight==-1 || rightHeight==-1 || Math.abs(leftHeight-rightHeight)>1)
           return -1;
       return Math.max(leftHeight,rightHeight)+1;
   }

总结

首先掌握平衡树的判断标准，不能用最大深度减去最小深度来进行计算。需要递归判断左右子树的高度差，当递归到高度差大于1的时候递归往上返回-1值。递归到null时，说明到达了叶子结点的下的空节点，返回0。其他情况都返回左右节点的最大高度加1。